The invention relates to the management of connections to mobile units in wireless communications systems and, in particular, wireless cellular communications systems.
Wireless cellular communication systems require efficient mobility management algorithms to cope with frequent handoffs and rerouting of connections, as the mobile units frequently change their points of attachment to the network. Consequently, one of the key challenges for the designers and managers of such systems is to develop a system, which adapts to the mobile unit""s mobility by managing connections efficiently in a manner that ensures that an acceptable quality of service (QoS) is provided to the mobile unit.
Mobility management entails both connection management and location management. Connection Management contains both a connection-establishment phase prior to data exchange and a connection-release phase after data exchange. In a wireless network, as mobile units move through cells of the network, connections have to be torn down and re-established with a frequency that corresponds to the speed of the mobile through the cells. Managing the connection during a transition from one cell to another while maintaining the integrity of the data, includes preserving the packet sequencing, preventing packet duplication and avoiding loss of packets.
At the most fundamental level of QoS requirements, is the ability of the network to maintain connectivity with the mobile unit even when the terminal frequently changes its physical location. It is possible to maintain connectivity with the mobile unit and guarantee a certain QoS to it if the network knows prior to the mobile""s movement the exact trajectory it will follow. With this information, the network can determine if there are enough resources available along the mobile""s path for the lifetime of the connection. If such is the case, the network anticipates the mobile""s demands and takes appropriate steps such as setting up end-to-end routes, reserving resources along these routes and planning quick low-latency handoffs between base stations of adjacent cells. With these kinds of preparations QoS can be guaranteed.
An approach for providing QoS to mobile terminals was recently proposed by A. Acampora and M. Naghshineh, in their paper xe2x80x9cAn Architecture and Methodology for Mobile-Executed Hand-off in Cellular ATM Networks,xe2x80x9d published in the IEEE Journal on Selected Areas in Communications, Vol. 12, No. 4, October 1994, pp. 1365-1375. In this paper the authors propose a technique called the virtual connection tree (VCT) scheme in which connections are pre-established between a fixed (root) switch and a set of base stations with whom the mobile could potentially connect. The VCT approach maintains QoS by pre-establishing end-to-end connections from the base stations with which the mobile unit could potentially attach, and consequently by minimizing handoff latency between base stations (i.e., the time between initiation and completion of the hand off) and by minimizing packet loss, which interrupts the connection. Unfortunately, the VCT approach results in inefficient use of network resources, is a potential source for overloading the network, and requires substantial processing time for setting up and assigning the Virtual Connections (VC). Network inefficiencies occur since the VCs are pre-assigned without accurately taking into account the mobile""s current and projected movement patterns. Consequently, many pre-assigned VCs are wasted and efficient resource reservation cannot be achieved.
The VCT approach suffers from the lack of accurate knowledge of the mobile""s trajectory. As a result, there is a substantial risk that the connection resources at the base stations will be under utilized, with the mobile never connecting to a reserved channel and potentially overloading the base stations with large numbers of unused reserved channels. Overloading can lead to traffic congestion in a cell, which may result in the base stations either dropping or buffering a connection. Buffering can cause temporary violations of the network""s delay and cell loss guarantees and can effect QoS.
As a possible solution to these kinds of problems caused by the VCT approach, the concept of a Shadow Cluster has been proposed. A Shadow Cluster defines the area of influence of a mobile terminal (i.e. a set of base stations or network cells to which the mobile unit is likely to attach in the near future). Like a shadow, this set moves along with the mobile, incorporating new base stations while leaving the old ones as they come under and out of the mobile""s influence. Each base station in the Shadow Cluster anticipates the mobile""s arrival and reserves resources for it. A close association exists between the predicted time the mobile will arrive at one of the cells of the Shadow Cluster and the time when the cell""s resources are reserved. The accuracy of the prediction of the mobile""s path determines the number of base stations in which resources are actually reserved and consequently determines the overall network overhead required to maintain the desired QoS.
Location management or location tracking incorporates a set of mechanisms with which the network can locate a particular mobile at any given time. Location updating and location prediction are two strategies that can possibly be used to implement mechanisms for locating a mobile. Location updating is a passive strategy in which the network periodically records the current location of the mobile in a database. Thus, the proficiency of the mobile tracking algorithm depends on the frequency with which the location of the mobile is updated, which in most network systems is controlled by the mobile. In contrast, location prediction is a dynamic strategy in which the network system estimates the mobile""s location based on a model of the mobile""s movement. The proficiency of the tracking depends on the accuracy of the model and the accuracy of the algorithm used to predict the future movement of the mobile.
While most recent studies have focused on the updating method, relatively little has been done with respect to the prediction approach. As a consequence, management or tracking of a mobile is generally treated as purely a process of updating and querying databases. If accurate prediction of the movement of a mobile was possible, the task of locating mobiles given their last location would become substantially more efficient in terms of both speed and use of system resources.
One way for the network to know the future direction of the mobile is to have a formal mechanism in place that allows the mobile user to indicate to the system his or her intended destination and the duration of the connection. The network can then combine this information with its knowledge of the geography of the terrain and the location of the base stations within the terrain to determine the cellular path of the mobile. Unfortunately, this is not an all-encompassing solution since there may be multiple paths to a destination. Even after using the general direction information provided by the mobile the system cannot exactly determine which one of the multiple paths the mobile will follow on every occasion. It is reasonable to expect that the mobile may diverge from a system selected route without warning in order to adjust to a dynamically changing environment around it. Without the network also dynamically adapting to such a change in the expected cellular route, the amount of resources required to provide improved connectivity is prohibitively great and consequently unattractive and possibly even impractical.
Some previous works in the area of mobility trajectory prediction include a suggestion that the mobile""s location be determined based on a behavior model represented as a set of historical movement patterns stored in a user profile. This model can be further refined to be modeled as repetitions of some elementary historical movement patterns of the mobile. Based on these movement patterns, a mobile motion prediction (MMP) algorithm matches the historical patterns to the actual pattern and then predicts or estimates the future location of the mobile. The main drawback of the MMP algorithm is its high sensitivity to the so called xe2x80x9crandom movements.xe2x80x9d Any movement of the mobile that cannot be classified by the mobility patterns defined in the user profile is classified as random movement. The accuracy of the prediction of the future location of the mobile by the MMP algorithm decreases linearly with the increase in the random factor (xcex3).
Other methods for predicting a future location and speed of the mobile have been attempted using speed and trajectory, but these have generally been limited in scope since they consider rectilinear (xe2x80x9chighwayxe2x80x9d) movement patterns only.
The invention is directed to a system and method for managing resources in a wireless cellular communications system wherein both intra-cell and inter-cell trajectory of the mobile unit are monitored and subsequently used to predict the path it will take for the purposes of reserving bandwidth and setting up routes ahead of time, reducing hand-off latencies, and relieving congestion in the cells along this predicted path. The invention provides a mechanism that combines together a well-known stochastic estimation technique to determine the mobile unit""s trajectory and speed at the intra-cellular level with approximate pattern matching technique at the inter-cellular level to substantially increase the system""s ability to correctly predict the entire route of the mobile. By enhancing its ability to correctly predict the path of the mobile, the system provides enhanced uninterrupted service to the mobile while consuming minimal resources from the network. This hierarchical relationship is based on a two-tier scheme that combines location updating with location prediction to enhance connection management functions.
By predicting the route the mobile unit will take, the network is able to reserve bandwidth and set up virtual end-to-end connections from the base stations that are in the predicted path of the mobile""s route thus ensuring uninterrupted service for the entire duration of the connection. In order to ensure that bandwidth is not needlessly reserved, however, the network reserves resources in each cell along the predicted route based on an estimated time of arrival, for the mobile station into each of the cells. The estimated time of arrival is derived from the signal strength measurements and history of the mobile station. The signal strength measurement is preferably processed by the Kalman estimator in the mobile unit.
The signal strength as measured at the mobile unit is delivered to a prediction engine that is preferably on-board the mobile. The prediction engine tracks the path of the mobile and compares this with previous routes that the mobile has followed as recorded and stored in a memory, which is also preferably on-board the mobile unit. At the prediction engine, the current path of the mobile is referred to herein as the user""s actual path (UAP). The prediction engine then matches the UAP to one of the stored previous routes. The stored previous routes are called the User""s Mobility Patterns or xe2x80x9cUMPs.xe2x80x9d If no exact match is found, the prediction engine edits the stored UMPs in an attempt to match them to the UAP. The process of editing a UMP includes adding, deleting, or changing one of more cells identity in the UMP. If the amount of editing required to match one of the UMPs to the present path or UAP exceeds a threshold, the UAP is assumed to be new. If the path is a new one, only the Kalman processing of signal strengths that is part of the intra-cell trajectory calculation is relied upon to predict the path of the mobile, which results in the prediction being limited to only the next cell the unit will enter. Otherwise, the UMP that best matches the UAP is used to predict the mobile""s future movement, which the system then uses to coordinate bandwidth reservation.
The intra-cell trajectory of the mobile unit is preferably derived from the strengths of the radio signals (RSS) from surrounding base stations. The intra-cell trajectory is used to predict the next cell the mobile unit will enter. By adding the projected next cell to the history of the cellular path of the present connection, the reliability of predicting the overall route of the mobile for the present connection is enhanced considerably. The enhancement is particularly effective in situations where two or more UMPs partially overlap. When the overlapping UMPs diverge, the intra-cell trajectory provides important information for correctly predicting the correct next cell and thus the correct UMP as the predicted route.
Preferably, the prediction of the mobile""s future movement during a connection is made by the mobile station. However, the prediction can alternatively be done by the network. For reasons of personal security, however, the UMPs are preferably only maintained at the mobile.
The mobile station communicates the prediction to the network manager, which uses the prediction with the current trajectory of the mobile to manage its communications resourcesxe2x80x94i.e., the bandwidth of the base stations. The network manager reserves bandwidth in the base stations of cells along the projected route defined by the UMP so that hand-offs of the mobile unit from one base station to another is accomplished efficiently and with minimal degradation of the quality of the communications link. By reserving bandwidth, the network substantially decreases the chances that the connection between the mobile unit and the network will be dropped in an attempted hand-off.
To further enhance the QoS, the invention contemplates that in the case of traffic congestion if a channel is to be borrowed from another cell, the network preferentially borrows channels from cells along the predicted path. By borrowing a channel from the next cell along the predicted route, the network can overcome congestion in the current cell while circumventing the need for hand-offs as the mobile moves into the next cell, thus the quality of the connection is enhanced with a minimum amount of added overhead to the management of the network.
The invention also contemplates assigning a mobile to a base station that is adjacent to one of the cells in the predicted path. If the predicted path through a network cell is in a fringe area where the signals of adjacent cells overlap, the network may elect to reserve bandwidth in the cell that has the lesser amount of traffic. When the mobile enters the predicted cell with the higher amount of traffic, the network will coordinate a handoff to the adjacent cell, which has bandwidth reserved for the mobile in keeping with the invention.
In keeping with the two-tier scheme for predicting the path of a mobile, the prediction mechanism has two main components: (1) global prediction and (2) local prediction. For global prediction, an approximate pattern matching technique abstracts the geometric similarity between the UAP and the stored UMPs, none of which may exactly match the UAP. Using this pattern matching technique, only a few UMPS have to be stored. Each UMP can represent a number of mobility patterns, while maintaining accurate inter-cell prediction.
For local prediction, classical stochastic signal processing techniques are employed to extract user mobility information from noisy measurements. A self-adaptive extended Kalman filter provides a high degree of accuracy for next cell location and instantaneous speed prediction. Local prediction is independent of global prediction so that reasonably accurate short-distance prediction can be obtained even when the system has no knowledge of the user""s historical mobility patterns.
Finally, the invention is independent of the architecture of the underlying wireless cellular communications system such as ATM systems. Four strategies, prediction-based dynamic virtual connection trees (PVCT), prediction-based dynamic location update, Congestion relief using line of path channel borrowing and handoff management for mobile units in cellular systems are examples of deployable predictive mobility management in wireless cellular communications systems that are described hereinafter.
A better understanding of the advantages, features, properties and relationships of the invention will be obtained from the following detailed description and accompanying drawings which set forth an illustrative embodiment which is indicative of the various ways in which the principles of the invention may be employed.